Nash-Williams theorem
In graph theory, the Nash-Williams theorem is a tree-packing theorem that describes how many edge-disjoint spanning trees (and more generally forests) a graph can have:
A graph G has t edge-disjoint spanning trees iff for every partition [math]\displaystyle{ V_1, \ldots, V_k \subset V(G) }[/math] where [math]\displaystyle{ V_i \neq \emptyset }[/math] there are at least t(k − 1) crossing edges (Tutte 1961, Nash-Williams 1961).[1]
For this article, we will say that such a graph has arboricity t or is t-arboric. (The actual definition of arboricity is slightly different and applies to forests rather than trees.)
Related tree-packing properties
A k-arboric graph is necessarily k-edge connected. The converse is not true.
As a corollary of NW, every 2k-edge connected graph is k-arboric.
Both NW and Menger's theorem characterize when a graph has k edge-disjoint paths between two vertices.
Nash-Williams theorem for forests
NW (1964) generalized the above result to forests:
G can be partitioned into t edge-disjoint forests iff for every [math]\displaystyle{ U \subset V(G) }[/math], the induced subgraph G[U] has at most [math]\displaystyle{ t(|U|-1) }[/math] edges.
This is how people usually define what it means for a graph to be t-aboric.
In other words, for every subgraph S = G[U], we have [math]\displaystyle{ t \geq \lceil E(S) / (V(S) - 1) \rceil }[/math]. It is tight in that there is a subgraph S that saturates the inequality (or else we can choose a smaller t). This leads to the following formula
[math]\displaystyle{ t = \lceil \max_{S \subset G} \frac{E(S)}{V(S) - 1} \rceil }[/math]
also referred to as the NW formula.
The general problem is to ask when a graph can be covered by edge-disjoint subgraphs.
See also
- Arboricity
- Bridge (cut edge)
- Matroid partitioning
- Menger's theorem
- Tree packing conjecture
References
- ↑ 1.0 1.1 Diestel, Reinhard, 1959– Verfasser. (2017-06-30). Graph theory. ISBN 9783662536216. OCLC 1048203362.
- ↑ Chen, Boliong; Matsumoto, Makoto; Wang, Jianfang; Zhang, Zhongfu; Zhang, Jianxun (1994-03-01). "A short proof of Nash-Williams' theorem for the arboricity of a graph" (in en). Graphs and Combinatorics 10 (1): 27–28. doi:10.1007/BF01202467. ISSN 1435-5914.
External links
- Paulson, Lawrence C. The Nash-Williams partition theorem (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)
 |  |
